import collections


class Solution(object):
    def balancedString(self, s):
        d = collections.defaultdict(int)
        n = len(s)
        m = n // 4
        left = 0
        while left < n:
            if d[s[left]] + 1 <= m:
                d[s[left]] += 1
                left += 1
            else:
                break
        if left == n:
            return 0
        else:
            left -= 1
            min_len = n - left - 1
            right = n - 1
            while left >= 0:
                d[s[right]] += 1
                while d[s[right]] > m and left >= 0:
                    d[s[left]] -= 1
                    left -= 1
                if d[s[right]] <= m:
                    min_len = min(min_len, right - left - 1)
                else:
                    break
                right -= 1
            while d[s[right]] + 1 <= m:
                d[s[right]] += 1
                min_len = min(min_len, right - left - 1)
                right -= 1
            return min_len

data = Solution()
s = 'QQWR'
print(data.balancedString(s))
data = Solution()
s = 'QQWR'
print(data.balancedString(s))